package com.ljy.my_study.lintcode.接雨水;
/** 
* @author James
* @date 2019年5月12日 
*/
public class TestMain {
//	给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。
//
//	Trapping Rain Water
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	样例 1:
//
//	输入: [0,1,0]
//	输出: 0
//	样例 2:
//
//	输入: [0,1,0,2,1,0,1,3,2,1,2,1]
//	输出: 6
//	挑战
//	O(n) 时间, O(1) 空间
//
//	O(n) 时间, O(n) 空间也可以接受
	public static void main(String[] args) {
//		int[] heights=new int[]{8644,1865,7993,3233,2267,7674,2465};
//		System.out.println(trapRainWater(heights));
		System.out.println(aPlusb(6,1));
	}
	
	public static int trapRainWater(int[] heights) {
		if(heights==null||heights.length<=2) return 0;
		int firstTop=0;
		int secondTop=0;
		int sum=0;
		out:while(secondTop<heights.length) {
			while(firstTop+1<heights.length&&heights[firstTop]<=heights[firstTop+1]) {
				firstTop++;
			}
			secondTop=firstTop;
			int newSecondTop=secondTop+1;
			for(int i=secondTop+1;i<heights.length;i++) {
				if(heights[i]>=heights[secondTop]) {
					secondTop=i;
					break;
				}
				if(heights[newSecondTop]<=heights[i]) {
					newSecondTop=i;
				}
				if(i==heights.length-1) {
					secondTop=newSecondTop;
				}
			}
			int start=firstTop+1;
			int end=secondTop;
			int top=Math.min(heights[firstTop],heights[secondTop]);
			while(start<end) {
				sum+=top-heights[start];
				start++;
			}
			if(start>end) return sum;
			firstTop=secondTop;
		}
		return sum;
    }
	
	public static int aPlusb(int a,int b) {
		int m=0;
		int n=0;
		while((n=a&b)!=0) {
			m=a^b;
			a=n<<1;
			b=m;
		}
		return a^b;
	}
	
}
